package E_2024;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/*
恢复数字序列
    对于一个连续正整数组成的序列，可以将其拼接成一个字符串，
    再将字符串里的部分字符打乱顺序。如序列8 9 10 11 12，
    拼接成的字符串为89101112，打乱一部分字符后得到90811211，
    原来的正整数10就被拆成了0和1。现给定一个按如上规则得到的打乱字符的字符串，
    请将其还原成连续正整数序列，并输出序列中最小的数字.
输入描述
    输入一行，为打乱字符的字符串和正整数序列的长度，两者间用空格分隔，
    字符审长度不超过200，正整数不超过1000，保证输入可以还原成唯一序列。
    【这里注意题目到底是1000还是10000】题目有微小的改动
输出描述
    输出一个数字，为序列中最小的数字
示例1：
    输入
    19801211 5
    输出
    8
    说明：正常的数字序列为8 9 10 11 12 这5个数字，最小数字为8
 */
public class E_100_55 {
    public static void main(String[] args) {
        System.out.println(ans("19801211",5));
    }
    // 使用滑动窗口答题
    // 需要确定滑动窗口起点
    public static int ans(String str, int length){
        int[] temp = new int[10];
        for (int i = 0; i < str.length(); i++) {
            int index = str.charAt(i) - '0';
            temp[index]++;
        }
        // 默认窗口直接从1开始
        int i = 1;
        while(true){
            if (temp[i%10] != 0) {
                int[] xp = Arrays.copyOf(temp,temp.length);
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < length; j++) {
                    sb.append(i+j);
                }
                if (sb.length() == str.length()){
                    int l = sb.length();
                    char[] chars = sb.toString().toCharArray();
                    for (char aChar : chars) {
                        if (xp[aChar - '0'] < 1) break;
                        l--;
                    }
                    if (l == 0) return i;
                }
            }
            i++;
        }
    }
    public static int ans1(String str, int length){
        int[] temp = new int[10];
        for (int i = 0; i < str.length(); i++) {
            int index = str.charAt(i) - '0';
            temp[index]++;
        }
        // 默认窗口直接从1开始
        int i = 1;
        while(true){
            if (temp[i%10] != 0) {
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < length; j++) {
                    sb.append(i+j);
                }
                if (sb.length() == str.length()){
                    char[] chars = sb.toString().toCharArray();
                    char[] strA = str.toCharArray();
                    Arrays.sort(chars);
                    Arrays.sort(strA);
                    if (Arrays.equals(chars, strA)) return i;
                }
            }
            i++;
        }
    }
}
